package com.lw.leetcode.sort.b;

import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 220. 存在重复元素 III
 * 剑指 Offer II 057. 值和下标之差都在给定的范围内
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/28 22:16
 */
public class ContainsNearbyAlmostDuplicate {


    public static void main(String[] args) {
        ContainsNearbyAlmostDuplicate test = new ContainsNearbyAlmostDuplicate();
        // 输入：nums = [1,2,3,1], k = 3, t = 0
        //输出：true
        //示例 2：
        //
        //输入：nums = [1,0,1,1], k = 1, t = 2
        //输出：true
        //示例 3：
        //
        //输入：nums = [1,5,9,1,5,9], k = 2, t = 3
        //输出：false
        //
        //来源：力扣（LeetCode）
        //链接：https://leetcode-cn.com/problems/contains-duplicate-iii
        //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


        // true
//        int[] arr = {1,2,3,1};
//        int a = 3;
//        int b = 0;

        // true
//        int[] arr = {1,0,1,1};
//        int a = 1;
//        int b = 2;

        // false
//        int[] arr = {1,5,9,1,5,9};
//        int a = 2;
//        int b = 3;

        // false
        int[] arr = {-3, 3, -6};
        int a = 2;
        int b = 3;


        boolean b1 = test.containsNearbyAlmostDuplicate(arr, a, b);
        System.out.println(b1);
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        k++;
        int length = nums.length;
        int min = Math.min(length, k);
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < min; i++) {
            set.add((long) nums[i]);
        }
        if (set.size() < min) {
            return true;
        }
        long item = ((long) Integer.MIN_VALUE) << 3;
        for (Long v : set) {
            if (v - item <= t) {
                return true;
            }
            item = v;
        }
        for (int i = min; i < length; i++) {
            long n = nums[i];
            set.remove((long) nums[i - k]);
            Long floor = set.floor(n);
            if (floor != null && n - floor <= t) {
                return true;
            }
            Long ceiling = set.ceiling(n);
            if (ceiling != null && ceiling - n <= t) {
                return true;
            }
            set.add(n);
        }
        return false;
    }

}
